package com.kaigejava.sortingalgorithm.insertionsorting;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 *插入排序
 * 思想：
 * 把n个待排序的元素看成一个有序表和一个无序表。
 * 开始时的时候，有序表中只有1个元素，无序表含有N-1个元素。
 * 排序过程中每次从无序列表中取出一个元素，把它们排序依次
 */
public class InsertionSortingDemo {
    public static void main(String[] args) {
        int [] arr = {101,34,119,1,-1,89};
        System.out.println("排序前:"+ Arrays.toString(arr));
        insertionSortingFunction(arr);
        System.out.println("排序后:"+ Arrays.toString(arr));
    }

  /**
   * 把n个待排序的元素看成一个有序表和一个无序表。
   * 开始时的时候，有序表中只有1个元素，无序表含有N-1个元素。
   * 排序过程中每次从无序列表中取出一个元素，把它们排序依次
   */
    private static void insertionSortingFunction(int[] arr) {
        int insertVal = 0 ;
        int insertIndex = 0;
        //for循环从1开始。因为默认有序列表中是第1个元素。也就是下标为0的
        for (int i = 1; i < arr.length; i++) {
            //待插入的数据是从下标为1的元素开始的
            insertVal = arr[i];
            //插入下标是从0开始的.是待插入值的下标的前一个
            insertIndex = i -1;
            //1:insertIndex >=0 保证在给insertVal找插入位置
            //2:insertVal = arr[insertIndex]
            //3:需要将arr[insertIndex]后移
            while(insertIndex >= 0 && insertVal <arr[insertIndex]){
                //交换位置
                arr[insertIndex +1 ] = arr[insertIndex];
                //交换万后，需要将inserIndex再减去1
                insertIndex -- ;
            }

            if(insertIndex +1 != i){
                //
                arr[insertIndex +1] = insertVal;
            }


        }



    }
}
